The present invention relates to a method and apparatus for producing a delayed version of a sequence of bits, and, more particularly, to a method and apparatus for producing a delayed version of a maximum length sequence output from a linear feedback shift register.
Linear feedback shift registers (LFSR's) are employed in a variety of applications, including generating the pseudo-random spreading codes used in code division multiple access (CDMA) transmission systems. In CDMA systems a need arises to produce a specified maximum length sequence with an arbitrary delay. For example, the receiver's linear feedback shift register must be set up to generate the same pseudo-random spreading code sequence as that of the transmitter. This is a necessary, but not sufficient, condition to enable reception of the transmitted signals. The receiver does this by using the precise transmitter time offset. Thus, an important function which the receiver must perform is to produce the specified maximum length sequence from the linear feedback shift register with an arbitrary delay.
A maximum length sequence of order m is a sequence of 2.sup.m -1 binary digits (bits) such that the smallest continually repeating pattern within the sequence is the sequence itself. A first maximum length sequence which is delayed by an arbitrary delay value q, such that 0.ltoreq.q&lt;2.sup.m -1, is a second maximum length sequence which is identical to the first maximum length sequence, except that the bits of the second maximum length sequence are offset by q bit positions from the corresponding bits of the first maximum length sequence.
A linear feedback shift register of m stages generates certain elements of a finite Galois field of order 2.sup.m. (A concise summary of linear feedback shift registers is given by Beker and Piper in Cipher Systems, Wiley-Interscience, 1982.) Galois fields of order 2.sup.m may be represented by binary polynomials expressed in terms of a polynomial argument, hereinafter denoted as "x", with modulo addition and modulo multiplication defined using a primitive polynomial as the modulus. A primitive polynomial is a polynomial which does not factor and divides x.sup.T +1, where T=2.sup.m -1. The addition operation on a Galois field of order 2.sup.m, denoted by `+`, is equivalent to the binary exclusive-OR operation. Multiplication by x in a Galois field of order 2.sup.m is a modulo left-shift of the binary digits representing the polynomial multiplicand. All the 2.sup.m -1 non-zero elements of a Galois field of order 2.sup.m may be produced by successive powers of a particular element, usually chosen to be x. With the inclusion of the zero element, there are thus a total of 2.sup.m elements in such a field.
FIG. 1 illustrates the prior art Galois form of a linear feedback shift register. The m stages of the LFSR are flip-flops containing the states of the m terms of the polynomial representing the current state. The zero-order term of the state a.sub.0 is a flip-flop 14, the .alpha..sub.m-2 term is a flip-flop 12, and the .alpha..sub.m-1 term is a flip-flop 10. The ellipsis . . . indicates intermediate stages not shown, and it is understood that the descriptions illustrated here for the stages shown also apply to the stages not shown. The corresponding polynomial that is represented by that state is .alpha..sub.0 x.sup.m-1 +. . . +.alpha..sub.m-1 x.sup.0. The LFSR sequence output 19 is a.sub.0 from flip-flop 14, which is also fed to a series of weighted taps 18, 20, and 22. The weights are either 0 or 1, and represent the coefficients of a generator polynomial. For example, tap 18 is set according to the coefficient g.sub.1, tap 20 is set according to the coefficient g.sub.2, and tap 22 is set according to the coefficient g.sub.m-1. If the generator polynomial is a primitive polynomial over the Galois field, then the output of the LFSR will be a maximum length sequence. Each bit position of the sequence output corresponds to a clock pulse, and all flip-flops receive input clock pulses simultaneously on a common line 17. Each flip-flop stores the value input therein at each successive clock pulse and presents the value stored therein as an output to the next flip-flop. Between pairs of flip-flops are modulo 2 adders 16 which combine the weighted sequence output of the LFSR with the output from the previous flip-flop of the pair. Each successive bit position of a sequence output from a linear feedback shift register corresponds to a successive state of the linear feedback shift register, which in turn corresponds to a successive clock pulse by which the state of the linear feedback shift register is advanced. The present application uses the term "clock time" to denote the integer which represents the number of a particular clock pulse. Clock time is used to reference the state of a linear feedback shift register as well as a bit position within a particular sequence.
The state of a linear feedback shift register at a clock time k is specified by the states of the flip-flops .alpha..sub.0, .alpha..sub.1, . . . , .alpha..sub.m-2, .alpha..sub.m-1, at clock time k. These states may be preset at state inputs 11, 13, and 15. The state may be written as a column vector: EQU a=[.alpha..sub.0 .alpha..sub.1 . . . .alpha..sub.m-2 .alpha..sub.m-1 ].sup.T(1)
It is noted that mathematically, a polynomial may be represented as a vector, and for computational purposes in this field of art, the two forms are often interchanged. The elements of a vector are generally referred to as "components," whereas the equivalent elements in the polynomial are the "coefficients" of the powers of the variable used in the polynomial. Therefore, the present application uses the terms "component" and "coefficient" to refer equivalently to the same computational entity, whether in respect to a vector or to a polynomial.
The sequence of bits in the sequence output from a linear feedback shift register is determined by the settings of the weighted taps and the initial state. The trivial initial state of a=0 will generate the trivial sequence of all zeros (a zero output with a period of one). Different non-trivial initial states will generate the same sequence of bits, although the outputs for different non-trivial initial states will be delayed by different amounts. The trivial sequence is of no interest, and therefore the present application hereinafter uses the term "initial state" to denote one of the 2.sup.m -1 non-trivial initial states. The sequence of bits output from a linear feedback shift register has the maximum period of 2.sup.m -1 if the weighted taps correspond to the coefficients of a primitive polynomial. Primitive polynomials always have g.sub.0 =g.sub.m =1, and therefore the weighted taps corresponding to the respective coefficients are simply direct connections. A sequence of maximum period is referred to as a maximum length sequence, or an m-sequence. For a linear feedback shift register whose weighted taps are set up to generate an m-sequence, the 2.sup.m -1 different initial states will generate the m-sequence with every one of the 2.sup.m -1 possible delays.
If the state of a linear feedback shift register at a clock time l is denoted by a.sup.(l), then the following recursion holds: EQU a.sup.(l+1) =Ma.sup.(l) (2)
where M is the transition matrix ##EQU1##
One way to produce a delayed version of a sequence is to use a linear feedback shift register with a mask that multiplies the cell values of the linear feedback shift register according to a plurality of inputs corresponding to the stages of the linear feedback shift register. That is, a linear feedback shift register of m stages will utilize a mask with m inputs. FIG. 2 illustrates the prior art use of such a linear feedback shift register with a mask, which is implemented by a plurality of AND gates 26. Each of the AND gates 26 has an input from each output of the m flip-flops which make up the LFSR. The other inputs of AND gates 26 are the mask coefficients b.sub.m-1, b.sub.m-2, . . . b.sub.1, and b.sub.0. The outputs of AND gates 26 are fed into a binary adder 28, whose output is c. The output c is the same as the sequence output of the LFSR except that it is delayed by a certain amount. For example, a simple but importance case is b.sup.(0) =[10 . . . 0 0].sup.T (b.sub.0 =1 and b.sub.1 =b.sub.2 = . . . =b.sub.m-2 =b.sub.-1 =0). For this case, the output c will be the same as .alpha..sub.0 ; that is, there will be no delay. The problem of producing an arbitrary delay, therefore, becomes that of selecting the mask components b.sub.0, b.sub.1, b.sub.2, . . . , b.sub.m-2, and b.sub.m-1 which will produce the desired arbitrary delay.
For conceptual simplicity in developing the mathematical formalism, the present application uses negative values of delay. A negative delay is an advance, so the problem is transformed into finding the mask b.sup.(q) which yields the sequence advanced by q clock pulses. Since the sequence is periodic, searching for a time offset can be done either by a delay or by an advance. If the sequence length is 2.sup.m -1 (such as for a maximum length sequence), an advance of q and a delay of 2.sup.m -1-q produce the same result. The present application uses the term "offset" to denote an integer number of bit positions by which one sequence is delayed with respect to another otherwise identical sequence, but without regard to which of the two sequences has been delayed. Thus, an advance of q bit positions and a delay of q bit positions are both offsets of q bit positions.
Starting from the state a.sup.0, the linear feedback shift register state advanced by q clock pulses from a.sup.0 is a.sup.(q), which can be found by iterating Equation (2), and using the matrix of Equation (3): EQU a.sup.(q) =M.sup.q a.sup.(0) (4)
Because the output is from a.sub.0, the advanced output will be given by EQU .alpha..sub.0.sup.(q) [10 . . . 00]M.sup.q a.sup.(0) (5)
Hence, the mask b.sup.(q) for the sequence advanced by q is obtained by: ##EQU2##
The method of Equation (6), that of matrix exponentiation, is the current prior art method of obtaining the mask b.sup.(q) for an arbitrary clock time advance of q clock pulses. That is, to obtain the mask for an arbitrary advance of q clock pulses, it is sufficient to raise the transpose matrix M.sup.T to the power q, because the desired mask b.sup.(q) is simply the first column of (M.sup.T).sup.q. Toward this end, certain improvements have been made in implementing matrix exponentiation. For example, U.S. Pat. No. 5,532,695 discloses a circuit arrangement for fast matrix multiplication. Nevertheless, matrix multiplication still involves considerable computation. When this is compounded by the need to raise a matrix to a power, the computation burden is correspondingly increased, even for efficient algorithms, and is a barrier to increased performance.
There is thus a widely recognized need for, and it would be highly advantageous to have, a method which efficiently produces a version of a maximum length sequence output of a linear feedback shift register with an arbitrary delay. This goal is met by the present invention.